package com.fengye.algorithms.alibaba;

/**
 * 思路：有多种解法，要求查找效率最高
 * 解法 1：由于数组本身有顺序没必要全部再排序，可以定义两个游标分别指向两个有
 * 序数组，按序移动，并用 count 计数，当 count 等于 k 时，返回两个游标指向的数
 * 中较小的那一个，时间复杂度 O(m+n)，不是最优解
 * 解法 2：充分利用两个数组都是有序的条件：
 * 1）当 array1[k/2-1] == array2[k/2-1] 则返回 array1[k/2-1] 或者 array2[k/2-1]
 * 2）当 array1[k/2-1] > array2[k/2-1]  则 array2 在 [0,k/2-1] 范围内的元素一定比
 * array1、array2 合并后第 k 个元素小，可以不用考虑 array2 在 [0,k/2-1] 范围内
 * 的元素
 * 3）当 array1[k/2-1] < array2[k/2-1]  则 array1 在 [0,k/2-1] 范围内的元素一定比
 * array1、array2 合并后第 k 个元素小，可以不用考虑 array1 在 [0,k/2-1] 范围内
 * 的元素
 * 因此算法可以写成一个递归的形式，递归结束的条件为：
 * 1）array1[k/2-1] == array2[k/2-1] return array1[k/2-1] -- 这里会相等？？？？
 * 2）array1 或者 array2 为空时，return array1[k-1] 或者 array2[k-1]
 * 3）k==1 时，返回 min(array1[0],array2[0])
 * 时间复杂度 O(log(m+n))
 * @Author fengye
 * @Date 2023/4/12 18:58
 **/
public class SortArrayKNumber28 {
    public static int findKth(int[] arr1, int[] arr2, int k) {
        if(arr1 == null || arr1.length < 1)
            return arr2[k-1];
        if(arr2 == null || arr2.length < 1)
            return arr1[k-1];
        // 注意这个函数的参数有7个，上面那个函数的参数只有3个，同名不同函数哈
        return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);
    }

    public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
        // 递归结束条件
        if(l1 > r1)
            return arr2[l2 + k];
        if(l2 > r2)
            return arr1[l1 + k];
        if (k == 0)// 注意，k == 0的结束条件与上面两个结束条件不能颠倒。
            return Math.min(arr1[l1],arr2[l2]);
        int md1 = l1 + k/2 < r1 ? l1 + k/2 : r1;
        int md2 = l2 + k/2 < (r2 - l1) ? l2 + k/2 : r2;
        if(arr1[md1] < arr2[md2])
            return findKth(arr1, md1 + 1, r1, arr2, l2, r2, k - k / 2 - 1);
        else if (arr1[md1] > arr2[md2])
            return findKth(arr1, l1, r1, arr2, md2 + 1, r2, k - k / 2 - 1);
        else
            return arr1[md1];//返回arr2[md2]也可以，一样的。
    }

    // 测试
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {0,4, 5, 6, 7, 8};
        // 现在还是有问题的
        System.out.println(findKth(arr1, arr2, 7));
    }
}
